package com.lili.backtrack;

import java.util.*;

/**
 * @Auther: 李 力
 * @Date: 2024/8/21
 * @Description: N皇后问题
 * @version: 1.0
 */
public class LeetCode51 {
    public static List<List<String>> solveNQueens(int n) {
        boolean[] ca = new boolean[n];//记录冲突列
        boolean[] cb = new boolean[2 * n - 1];//记录左边斜线冲突
        boolean[] cc = new boolean[2 * n - 1];//记录右斜线冲突
        char[][] table = new char[n][n];//'.','Q'
        for (char[] ch : table) {
            Arrays.fill(ch, '.');
        }
        List<List<String>> result = new ArrayList<>();
        dfs(0, n, table, ca, cb, cc, result);
        return result;
    }

    private static void dfs(int i, int n,
                            char[][] table,
                            boolean[] ca, boolean[] cb, boolean[] cc,
                            List<List<String>> result) {
        if (i == n) {
            List<String> str = new ArrayList<>();
            for (char[] chars : table) {
                str.add(new String(chars));
            }
            result.add(str);
            return;
        }
        for (int j = 0; j < n; j++) {
            if (ca[j] || cb[i + j] || cc[n - 1 - (i - j)]) {
                continue;
            }
            table[i][j] = 'Q';
            ca[j] = true;
            cb[i + j] = true;
            cc[n - 1 - (i - j)] = true;
            dfs(i + 1, n, table, ca, cb, cc, result);
            table[i][j] = '.';
            ca[j] = false;
            cb[i + j] = false;
            cc[n - 1 - (i - j)] = false;
        }
    }

}
